Control-Flow Analysis in Cubic Time
Identifieur interne : 000224 ( LNCS/Analysis ); précédent : 000223; suivant : 000225Control-Flow Analysis in Cubic Time
Auteurs : Flemming Nielson [Danemark] ; Helmut Seidl [Allemagne]Source :
- Lecture Notes in Computer Science [ 0302-9743 ] ; 2001.
Descripteurs français
- Pascal (Inist)
English descriptors
- KwdEn :
Abstract
Abstract: It is well-known that context-independent control flow analysis can be performed in cubic time for functional and object-oriented languages. Yet recent applications of control flow analysis to calculi of computation (like the π-calculus and the ambient calculus) have reported considerably higher complexities. In this paper we introduce two general techniques, the use of Horn clauses with sharing and the use of tiling of Horn clauses, for reducing the worst-case complexity of analyses. Applying these techniques to the π-calculus and the ambient calculus we reduce the complexity from O(n 5) to O(n 3) in both cases.
Url:
DOI: 10.1007/3-540-45309-1_17
Affiliations:
Links toward previous steps (curation, corpus...)
- to stream Istex, to step Corpus: 001185
- to stream Istex, to step Curation: 001073
- to stream Istex, to step Checkpoint: 000C46
- to stream Main, to step Merge: 002116
- to stream PascalFrancis, to step Corpus: 000E42
- to stream PascalFrancis, to step Curation: 000115
- to stream PascalFrancis, to step Checkpoint: 000C08
- to stream Main, to step Merge: 002164
- to stream Main, to step Curation: 001E42
- to stream Main, to step Exploration: 001E42
- to stream LNCS, to step Extraction: 000224
Links to Exploration step
ISTEX:D42CAB5F9BF46B05D6F00A8FDD9F10633AF967DBLe document en format XML
<record><TEI wicri:istexFullTextTei="biblStruct"><teiHeader><fileDesc><titleStmt><title xml:lang="en">Control-Flow Analysis in Cubic Time</title><author><name sortKey="Nielson, Flemming" sort="Nielson, Flemming" uniqKey="Nielson F" first="Flemming" last="Nielson">Flemming Nielson</name></author><author><name sortKey="Seidl, Helmut" sort="Seidl, Helmut" uniqKey="Seidl H" first="Helmut" last="Seidl">Helmut Seidl</name></author></titleStmt><publicationStmt><idno type="wicri:source">ISTEX</idno><idno type="RBID">ISTEX:D42CAB5F9BF46B05D6F00A8FDD9F10633AF967DB</idno><date when="2001" year="2001">2001</date><idno type="doi">10.1007/3-540-45309-1_17</idno><idno type="url">https://api.istex.fr/document/D42CAB5F9BF46B05D6F00A8FDD9F10633AF967DB/fulltext/pdf</idno><idno type="wicri:Area/Istex/Corpus">001185</idno><idno type="wicri:explorRef" wicri:stream="Istex" wicri:step="Corpus" wicri:corpus="ISTEX">001185</idno><idno type="wicri:Area/Istex/Curation">001073</idno><idno type="wicri:Area/Istex/Checkpoint">000C46</idno><idno type="wicri:explorRef" wicri:stream="Istex" wicri:step="Checkpoint">000C46</idno><idno type="wicri:doubleKey">0302-9743:2001:Nielson F:control:flow:analysis</idno><idno type="wicri:Area/Main/Merge">002116</idno><idno type="wicri:source">INIST</idno><idno type="RBID">Pascal:01-0247617</idno><idno type="wicri:Area/PascalFrancis/Corpus">000E42</idno><idno type="wicri:Area/PascalFrancis/Curation">000115</idno><idno type="wicri:Area/PascalFrancis/Checkpoint">000C08</idno><idno type="wicri:explorRef" wicri:stream="PascalFrancis" wicri:step="Checkpoint">000C08</idno><idno type="wicri:doubleKey">0302-9743:2001:Nielson F:control:flow:analysis</idno><idno type="wicri:Area/Main/Merge">002164</idno><idno type="wicri:Area/Main/Curation">001E42</idno><idno type="wicri:Area/Main/Exploration">001E42</idno><idno type="wicri:Area/LNCS/Extraction">000224</idno></publicationStmt><sourceDesc><biblStruct><analytic><title level="a" type="main" xml:lang="en">Control-Flow Analysis in Cubic Time</title><author><name sortKey="Nielson, Flemming" sort="Nielson, Flemming" uniqKey="Nielson F" first="Flemming" last="Nielson">Flemming Nielson</name><affiliation wicri:level="1"><country xml:lang="fr">Danemark</country><wicri:regionArea>Computer Science Department, Aarhus University, (Bldg. 540) Ny Munkegade, DK-8000, cAarhus C</wicri:regionArea><wicri:noRegion>cAarhus C</wicri:noRegion></affiliation><affiliation wicri:level="1"><country wicri:rule="url">Danemark</country></affiliation></author><author><name sortKey="Seidl, Helmut" sort="Seidl, Helmut" uniqKey="Seidl H" first="Helmut" last="Seidl">Helmut Seidl</name><affiliation wicri:level="1"><country xml:lang="fr">Allemagne</country><wicri:regionArea>FB IV ― Informatik, Universität Trier, D-54286, Trier</wicri:regionArea><wicri:noRegion>54286, Trier</wicri:noRegion><wicri:noRegion>Trier</wicri:noRegion></affiliation><affiliation wicri:level="1"><country wicri:rule="url">Allemagne</country></affiliation></author></analytic><monogr></monogr><series><title level="s">Lecture Notes in Computer Science</title><imprint><date>2001</date></imprint><idno type="ISSN">0302-9743</idno><idno type="ISSN">0302-9743</idno></series><idno type="istex">D42CAB5F9BF46B05D6F00A8FDD9F10633AF967DB</idno><idno type="DOI">10.1007/3-540-45309-1_17</idno><idno type="ChapterID">17</idno><idno type="ChapterID">Chap17</idno></biblStruct></sourceDesc><seriesStmt><idno type="ISSN">0302-9743</idno></seriesStmt></fileDesc><profileDesc><textClass><keywords scheme="KwdEn" xml:lang="en"><term>Flow control</term><term>Flow field</term><term>Horn clauses</term><term>Musical instrument</term><term>Object oriented</term><term>Program analysis</term><term>Tiling</term><term>Time analysis</term><term>Worst case method</term></keywords><keywords scheme="Pascal" xml:lang="fr"><term>Analyse programme</term><term>Analyse temporelle</term><term>Champ écoulement</term><term>Clause Horn</term><term>Commande écoulement</term><term>Instrument musique</term><term>Méthode cas pire</term><term>Orienté objet</term><term>Pavage</term></keywords></textClass><langUsage><language ident="en">en</language></langUsage></profileDesc></teiHeader><front><div type="abstract" xml:lang="en">Abstract: It is well-known that context-independent control flow analysis can be performed in cubic time for functional and object-oriented languages. Yet recent applications of control flow analysis to calculi of computation (like the π-calculus and the ambient calculus) have reported considerably higher complexities. In this paper we introduce two general techniques, the use of Horn clauses with sharing and the use of tiling of Horn clauses, for reducing the worst-case complexity of analyses. Applying these techniques to the π-calculus and the ambient calculus we reduce the complexity from O(n 5) to O(n 3) in both cases.</div></front></TEI><affiliations><list><country><li>Allemagne</li><li>Danemark</li></country></list><tree><country name="Danemark"><noRegion><name sortKey="Nielson, Flemming" sort="Nielson, Flemming" uniqKey="Nielson F" first="Flemming" last="Nielson">Flemming Nielson</name></noRegion><name sortKey="Nielson, Flemming" sort="Nielson, Flemming" uniqKey="Nielson F" first="Flemming" last="Nielson">Flemming Nielson</name></country><country name="Allemagne"><noRegion><name sortKey="Seidl, Helmut" sort="Seidl, Helmut" uniqKey="Seidl H" first="Helmut" last="Seidl">Helmut Seidl</name></noRegion><name sortKey="Seidl, Helmut" sort="Seidl, Helmut" uniqKey="Seidl H" first="Helmut" last="Seidl">Helmut Seidl</name></country></tree></affiliations></record>Pour manipuler ce document sous Unix (Dilib)
EXPLOR_STEP=$WICRI_ROOT/Wicri/Rhénanie/explor/UnivTrevesV1/Data/LNCS/Analysis
HfdSelect -h $EXPLOR_STEP/biblio.hfd -nk 000224 | SxmlIndent | more
Ou
HfdSelect -h $EXPLOR_AREA/Data/LNCS/Analysis/biblio.hfd -nk 000224 | SxmlIndent | more
Pour mettre un lien sur cette page dans le réseau Wicri
{{Explor lien
|wiki= Wicri/Rhénanie
|area= UnivTrevesV1
|flux= LNCS
|étape= Analysis
|type= RBID
|clé= ISTEX:D42CAB5F9BF46B05D6F00A8FDD9F10633AF967DB
|texte= Control-Flow Analysis in Cubic Time
}}
| This area was generated with Dilib version V0.6.31. |  |